/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.graph
 * author:David
 * Date:2015年8月21日上午11:47:07
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.graph;

import com.xuwei.base.graph.Iterator;
import com.xuwei.base.link.Node;
import com.xuwei.ext.exception.UnsupportedOpertation;

/**
 * 无向图
 * @author David
 * @since 2015年8月21日 上午11:47:07
 * @version 
 * @since JDK 1.6
 */
public class UndirectedGraph extends AbstractGraph {

	@Override
	public void remove(Vertex v) {
		super.remove(v);
	}

	@Override
	public void remove(Edge e) {
		super.remove(e);
	}

	@Override
	public Edge edgeFromTo(Vertex u, Vertex v) {
		Edge edge = null;
		if(u==v){
			return edge;
		}
		Iterator it = u.getAdjacentEdges().elements();
		for(it.first();!it.isDone();it.next()){
			Edge _edge = (Edge) it.currentItem();
			Vertex _vertex_1 = (Vertex) _edge.getFirstVexPosition().getData();
			Vertex _vertex_2 = (Vertex) _edge.getSecondVexPosition().getData();
			if((u==_vertex_1&&v==_vertex_2)||(u==_vertex_2&&v==_vertex_1)){
				edge = _edge;
				break;
			}
		}
		return edge;
	}

	@Override
	public Iterator adjVertexs(Vertex u) {
		LinkList list=u.getAdjacentEdges();
		Iterator it=list.elements();
		LinkList vlist=new LinkListDLNode();
		for(it.first();!it.isDone();it.next()){
			Edge e=(Edge)it.currentItem();
			Vertex v1=(Vertex) e.getFirstVexPosition().getData();
			Vertex v2=(Vertex) e.getSecondVexPosition().getData();
			if(v1!=u){
				vlist.insertLast(v1);
			}else{
				vlist.insertLast(v2);
			}
		
		}
		Iterator iterator=new LinkListIterator(vlist);
		return iterator;
	}

	@Override
	public void generateMST() throws UnsupportedOpertation {//【采用prim算法】
		resetVexStatus();//重置图中各顶点的状态信息
		resetEdgeType(); //重置途中各边的类型信息
		Iterator it = getVertex();
		Vertex v = (Vertex)it.currentItem();//选第一个顶点作为起点
		v.setToVisited();  //顶点v进入集合S
		//初始化顶点集合S到V-S各顶点的最短横切边
		for(it.first();!it.isDone();it.next()){
			Vertex u = (Vertex)it.currentItem();
			Edge e = edgeFromTo(v, u);
			setCrossEdge(u, e);//设置到达V-S中顶点u的最短横切边
		}
		for(int i=1;i<getVexNum();i++){//进行|V|-1次循环找到|V|-1条边
			Vertex k = selectMinVertex(it);//选择轻边在V-S中顶点k
			k.setToVisited();              //顶点k加入S
			Edge mst = getCrossEdge(k);     
			if(mst!=null){
				mst.setToMST();
			}
			//以k为中间顶点修改S到V-S中顶点的最短横切边
			Iterator adjIt = adjVertexs(k);//取出k的所有邻接点
			for(adjIt.first();!adjIt.isDone();adjIt.next()){
				Vertex adjV = (Vertex)adjIt.currentItem();
				Edge e = edgeFromTo(k, adjV);
				if(e.getWeight()<getCrossWeight(adjV)){//发现到达adjV更短的横切边
					setCrossEdge(adjV, e);
				}
			}//end for
		}//end for
	}
	
	@Override
	public int getType() {
		return 0;//无向图返回0
	}


}
